// 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

// 示例 1：

// 输入：s = "aab"
// 输出：[["a", "a", "b"], ["aa", "b"]]
// 示例 2：

// 输入：s = "a"
// 输出：[["a"]]

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
    // 判断回文
    const check = (str) => {
        for (let i = 0, j = str.length - 1; i < j; i++, j--) {
            if (str[i] !== str[j])
                return false;
        }
        return true;
    }

    let res = [], temp = [];

    const backTrack = (s, startIndex) => {
        if (startIndex >= s.length) {
            res.push(temp.slice());
            return;
        }

        for (let i = startIndex; i < s.length; i++) {
            if (check(s.substring(startIndex, i + 1))) {
                temp.push(s.substring(startIndex, i + 1));
            } else {
                continue;
            }
            backTrack(s, i + 1);
            temp.pop();
        }

    }

    backTrack(s, 0);
    return res;

};


